/*
 * @lc app=leetcode.cn id=102 lang=rust
 *
 * [102] 二叉树的层序遍历
 */
struct Solution;
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}
// @lc code=start
use std::cell::RefCell;
use std::collections::VecDeque;
use std::ops::Deref;
use std::rc::Rc;
impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut que: VecDeque<Rc<RefCell<TreeNode>>> = VecDeque::new();
        let mut vec: Vec<Vec<i32>> = vec![];
        if let Some(root) = root {
            que.push_back(Rc::clone(&root));
            vec.push(vec![root.deref().borrow().val]);
        }
        while !que.is_empty() {
            let size: usize = que.len();
            let mut layer_vec: Vec<i32> = Vec::new();

            for _ in 0..size {
                if let Some(head) = que.pop_front() {
                    if let Some(ref left) = head.deref().borrow().left {
                        que.push_back(Rc::clone(&left));
                        layer_vec.push(left.deref().borrow().val);
                    }
                    if let Some(ref right) = head.deref().borrow().right {
                        que.push_back(Rc::clone(&right));
                        layer_vec.push(right.deref().borrow().val);
                    }
                }
            }
            if layer_vec.len() > 0 {
                vec.push(layer_vec);
            }
        }
        vec
    }
}
// @lc code=end

mod tests {
    #[test]
    fn test() {
        use super::*;
        let mut root = TreeNode::new(3);
        let left = TreeNode::new(9);
        let mut right = TreeNode::new(20);
        let right_left = TreeNode::new(15);
        let right_right = TreeNode::new(7);
        right.left = Some(Rc::new(RefCell::new(right_left)));
        right.right = Some(Rc::new(RefCell::new(right_right)));
        root.left = Some(Rc::new(RefCell::new(left)));
        root.right = Some(Rc::new(RefCell::new(right)));
        let res = Solution::level_order(Some(Rc::new(RefCell::new(root))));
        assert_eq!(res, vec![vec![3], vec![9, 20], vec![15, 7]]);
    }
}
